import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1600 {

    Map<String,List<String>> map=new HashMap<>();
    Map<String,Integer> dead=new HashMap<>();
    String kingName;

    public Solution1600(String kingName) {
        map.put(kingName,new ArrayList<>());
        dead.put(kingName,0);
        this.kingName=kingName;
    }

    public void birth(String parentName, String childName) {
        List<String> list=map.get(parentName);
        list.add(childName);
        map.put(childName,new ArrayList<>());
        dead.put(childName,0);
    }

    public void death(String name) {
        dead.put(name,1);
    }

    public List<String> getInheritanceOrder() {
        List<String> ans=new ArrayList<>();
        dfs(kingName,ans);
        return ans;
    }

    void dfs(String name,List<String> ans){
        if (dead.get(name)==0){
            ans.add(name);
        }
        List<String> list=map.get(name);
        for (String s : list) {
            dfs(s,ans);
        }
    }

    public static void main(String[] args) {
        Solution1600 solution1600=new Solution1600("king");
        solution1600.birth("king", "andy");
        solution1600.birth("king", "bob");
        solution1600.birth("king", "catherine");
        solution1600.birth("andy", "matthew");
        solution1600.birth("bob", "alex");
        solution1600.birth("bob", "asha");
        System.out.println(solution1600.getInheritanceOrder());
        solution1600.death("bob");
        System.out.println(solution1600.getInheritanceOrder());
    }
}
